package dynamic;

import java.util.Arrays;
import java.util.stream.Collectors;

import org.junit.Test;

//二进制字符串中0和1的数量__最多__达到m,n的最大子集数
public class Ex474 {
    class Solution1 {
        public int findMaxForm1(String[] strs, int m, int n) {
            int[][] dict = new int[strs.length][2];
            for (int i = 0; i < strs.length; i++) {
                int one = count1(strs[i]);
                dict[i][1] = one;
                dict[i][0] = strs[i].length() - one;
            }
            return dfs(m, n, 0, 0, dict);
        }

        /* 
            变化量：m, n, idx, cur

        
        */

       /*  public int findMaxForm(String[] strs, int m, int n) {
            int[][] dict = new int[strs.length][2];
            for (int i = 0; i < strs.length; i++) {
                int one = count1(strs[i]);
                dict[i][1] = one;
                dict[i][0] = strs[i].length() - one;
            }
            int len = strs.length;
            int[][][] f = new int[m + 1][n + 1][len + 1];
            f[m][n][len] = 0;

        } */
        public int dfs(int m, int n, int idx, int cur, int[][] dict) {
            if (m == 0 && n == 0)
                return cur;
            if (idx == dict.length || cur == dict.length)
                return cur;
            int res = 0;
            if (m >= dict[idx][0] && n >= dict[idx][1]) {
                res = Math.max(res, dfs(m - dict[idx][0], n - dict[idx][1], idx + 1, cur + 1, dict));
            }
            res = Math.max(res, dfs(m, n, idx + 1, cur, dict));
            return res;
        }

        public int count1(String s) {
            int count = 0;
            for (char c : s.toCharArray()) {
                if (c - '0' == 1)
                    count++;
            }
            return count;
        }
    }

    //正解：转为0-1背包问题
    /* 
        每一步考虑要不要这个单词，背包容量为二维
        idx:0 len
        i : 0 m
        j: 0  n
    */
    public int findMaxForm1(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] f = new int[len + 1][m + 1][n + 1];
        f[len][m][n] = 0; //空间没有减少，因此为0
        for (int k = len - 1;  k >= 0; k--) {
            int[] cur = count(strs[k]);
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    f[k][i][j] = f[k + 1][i][j];
                    if (i >= cur[0] && j >= cur[1]) {
                        // key： 需要将拿了一个位置结果加一
                        f[k][i][j] = Math.max(f[k][i][j], f[k + 1][i - cur[0]][j - cur[1]] + 1);
                    }
                }
            }
        }
        return f[0][m][n];
    }


    
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] f = new int[m + 1][n + 1];
        f[m][n] = 0; //空间没有减少，因此为0
        for (int k = len - 1;  k >= 0; k--) {
            int[] cur = count(strs[k]);
            for (int i = m; i >= 0; i--) {
                for (int j = n; j >= 0; j--) {
                    if (i >= cur[0] && j >= cur[1]) {
                        // key： 需要将拿了一个位置结果加一
                        f[i][j] = Math.max(f[i][j], f[i - cur[0]][j - cur[1]] + 1);
                    }
                }
            }
        }
        return f[m][n];
    }

    public int[] count(String s) {
        int[] res = new int[2];
        for (char c: s.toCharArray()) {
            res[c - '0']++;
        }
        return res;
    }

    class Solution {
        public int count1(String s) {
            int count = 0;
            for (char c : s.toCharArray()) {
                if (c - '0' == 1)
                    count++;
            }
            return count;
        }

        public int findMaxForm(String[] strs, int m, int n) {
            int[][] dict = new int[strs.length][2];
            for (int i = 0; i < strs.length; i++) {
                int one = count1(strs[i]);
                dict[i][1] = one;
                dict[i][0] = strs[i].length() - one;
            }
            /* 
                1. m
                2. n
                3. idx
                4. cur (cur可能就是没有，也到了idx最大值)
            */
            int[][][][] f = new int[m + 1][n + 1][strs.length + 1][strs.length + 1];
            int len = strs.length;
            //已知解：m = n = 0，f[0][0][i][j] = j; idx = len&& i >= 0 && j >= 0, f[i][j][len][k] = k;
            for (int i = 0; i <= len; i++) {
                for (int j = 0; j <= len; j++) {
                    f[0][0][i][j] = j;
                }
            }

            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    for (int k = 0; k <= len; k++) {
                        f[i][j][len][k] = k;
                        f[i][j][k][len] = len;
                    }
                }
            }
            Arrays.stream(f[0][0][0]).boxed().collect(Collectors.toList());
            for (int k = len - 1; k >= 0; k--) {
                for (int l = len - 1; l >= 0; l--) {
                    for (int i = 1; i <= m; i++) {
                        for (int j = 1; j <= n; j++) {
                            f[i][j][k][l] = f[i][j][k + 1][l];
                            if (i >= dict[k][0] && j >= dict[k][1]) {
                                f[i][j][k][l] = Math.max(f[i][j][k][l], 
                                f[i - dict[k][0]][j - dict[k][1]][k + 1][l + 1]);
                            }
                        }
                    }
                }
            }
            System.out.println(Arrays.deepToString(f));;
            return f[m][n][0][0];
        }
    }

    /* 
    [4,5,1,6,2,7,3,8],4
[4,5,1,6,2,7,3,8],8
[4,5,1,6,2,7,3,8],10
[4,5,1,6,2,7,3,8],1
[4,5,1,6,2,7,3,8],0
[4,5,1,6,2,7,2,8],2
[],0

    [1,2,3,4]
[1,2,3,4,5,6,7,8]
[]
[1]
[]
[1,2]

    [1,2,3,4]
[]
[]
[1]
java.lang.NullPointerException
    
    */

    @Test
    public void test() {
        /*   
        ["10","0001","111001","1","0"]
        5
        3*/

        String[] strs = {"10","1","0"};
        Solution s = new Solution();
        int res = s.findMaxForm(strs, 1, 1);
    }
}
